
namespace AlgorithmInsertionSort {
    // show debug log
    const isDebug: boolean = true;

    function insertionSort(arr: number[]) {
        const len = arr.length;
        if (len <= 1) return;
        if (isDebug)
            console.log(`数组长度${len}，排序前数组：\n`, JSON.stringify(arr));
        // 第一个元素当作已序
        for (var i = 1; i < len; i++) {
            let tarPos = i - 1; // 目标位置(从当前位置前一个开始，向前查找)
            const val = arr[i]; // 当前数值(做替换准备)
            while (tarPos >= 0 && arr[tarPos] > val) {
                arr[tarPos + 1] = arr[tarPos];
                tarPos--;
            }
            // 指针停止，指针的下一个位置就是正确的序列位置
            arr[tarPos + 1] = val;
            if (isDebug)
                console.log(`从数组位置${i}开始搜索，目标元素位置为${tarPos + 1}，排序后数组：\n`, JSON.stringify(arr));
        }
        return arr;
    }


    function main() {
        const ary: number[] = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
        insertionSort(ary);
    }
    main();
}